package main

import (
	"fmt"
	"math"
)

type Node struct {
	val   int
	left  *Node
	right *Node
}

var max int //全局max

/*
给定一个二叉树的头结点head，路径可以从任意节点出发，到任意节点，求最大路径和
*/
func getMax(node *Node) int {
	res, _ := process5(node)
	return res
}

func process5(node *Node) (int, int) {
	v := node.val
	if node.left == nil && node.right == nil {
		return v, v
	}

	var LFromHeadMax, RFromHeadMax int
	var LAllMax, fromHeadMax1, RAllMax, fromHeadMax2 int = math.MinInt64, math.MinInt64, math.MinInt64, math.MinInt64

	//与n无关
	////左子树allMax
	////右子树allMax
	if node.left != nil {
		LAllMax, LFromHeadMax = process3(node.left)
		fromHeadMax1 = LFromHeadMax + v
	}
	if node.right != nil {
		RAllMax, RFromHeadMax = process3(node.right)
		fromHeadMax2 = RFromHeadMax + v
	}
	//与n有关
	////n自己
	////左子树加n
	////右子树加n
	////左+右子树+n
	LR := Max(Max(fromHeadMax1, fromHeadMax2), LFromHeadMax+RFromHeadMax+v)

	return Max(Max(Max(LAllMax, RAllMax), LR), v),
		Max(LR, v)
}

/*
给定一个二叉树的头结点head，路径可以从任意节点出发，必须向下走到任意节点，求最大路径和
*/
func getMaxFairCurrent(node *Node) int {
	res, _ := process4(node)
	return res
}

func process3(node *Node) (int, int) { // 取得以node为头结点的最长路径值（不包括自己，包括）
	v := node.val
	if node.left == nil && node.right == nil { //来到叶子节点
		return v, v
	}

	var LAllMax, LFromHeadMax, RAllMax, RFromHeadMax int
	var allMax1, fromHeadMax1, allMax2, fromHeadMax2 int = math.MinInt64, math.MinInt64, math.MinInt64, math.MinInt64

	if node.left != nil {
		LAllMax, LFromHeadMax = process3(node.left)
		fromHeadMax1 = LFromHeadMax + v
		if LAllMax == LFromHeadMax { // 左子节点是极值有关点
			if v >= 0 {
				allMax1 = LAllMax + v
			} else { // 则之后当前节点不再是极值相关点
				allMax1 = LAllMax
			}
		} else {
			allMax1 = LAllMax
		}
	}
	if node.right != nil {
		RAllMax, RFromHeadMax = process3(node.right)
		fromHeadMax2 = RFromHeadMax + v
		if RAllMax == RFromHeadMax {
			if v >= 0 {
				allMax2 = RAllMax + v
			} else {
				allMax2 = RAllMax
			}
		} else {
			allMax2 = RAllMax
		}
	}

	return Max(Max(Max(Max(allMax1, allMax2), fromHeadMax1), fromHeadMax2), v),
		Max(Max(fromHeadMax1, fromHeadMax2), v)
}

//优化
func process4(node *Node) (int, int) {
	v := node.val
	if node.left == nil && node.right == nil {
		return v, v
	}

	var LAllMax, LFromHeadMax, RAllMax, RFromHeadMax int
	var allMax1, fromHeadMax1, allMax2, fromHeadMax2 int = math.MinInt64, math.MinInt64, math.MinInt64, math.MinInt64

	if node.left != nil {
		LAllMax, LFromHeadMax = process3(node.left)
		fromHeadMax1 = LFromHeadMax + v // 不管该子节点是不是有关点，在fromHeadMax+v大于allMax后本节点就是相关点了
		allMax1 = LAllMax
	}
	if node.right != nil {
		RAllMax, RFromHeadMax = process3(node.right)
		fromHeadMax2 = RFromHeadMax + v
		allMax2 = RAllMax
	}

	return Max(Max(Max(Max(allMax1, allMax2), fromHeadMax1), fromHeadMax2), v),
		Max(Max(fromHeadMax1, fromHeadMax2), v)
}

/*
给定一个二叉树的头结点head，路径必须从头出发，到叶节点为止，求最大路径和
*/
func getMaxFromHeadToLeaf(node *Node) int {
	// return process2(node)
	process1(node, 0)
	return max
}

func process1(node *Node, cur int) { // 递归处理max
	cur = cur + node.val
	if node.left == nil && node.right == nil { //来到叶子节点
		max = Max(max, cur)
		return
	}
	if node.left != nil {
		process1(node.left, cur)
	}
	if node.right != nil {
		process1(node.right, cur)
	}
}

func process2(node *Node) int { // 取得以node为头结点的最长路径值
	if node.left == nil && node.right == nil { //来到叶子节点
		return node.val
	}
	var l, r int
	if node.left != nil {
		l = process2(node.left)
	}
	if node.right != nil {
		r = process2(node.right)
	}
	return Max(l, r) + node.val
}

func main() {
	bt1 := &Node{val: -3,
		left: &Node{val: -4,
			left: &Node{val: 9,
				left: &Node{val: -3,
					right: &Node{val: -5,
						right: &Node{val: 12}}}},
			right: &Node{val: 4}},
		right: &Node{val: 5,
			left:  &Node{val: -10},
			right: &Node{val: 3}}}

	// res := getMaxFromHeadToLeaf(bt1)
	// res := getMaxFairCurrent(bt1)
	res := getMax(bt1)
	fmt.Println(res)
}

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
